/**
 * 堆的操作
 *
 * “删除”就是“向下比较+交换”，而“添加”则是“向上比较+交换”。
 */

// 取出堆顶元素
function downHeap(low, heigh, heap) {
	// 初始化 i 为当前结点，j 为当前结点的左孩子
	let i = low
	let j = 2 * i + 1

	// 当 j 不超过上界时，重复向下对比+交换的操作
	while (j <= heigh) {
		// 判断左右孩子大小， 如果右孩子比左孩子更大，则用右孩子和根结点比较
		if (j + 1 < heigh && heap[j + 1] > heap[j]) {
			j += 1
		}

		// 若当前结点比孩子结点小，则交换两者的位置，把较大的结点“拱上去”
		if (heap[i] < heap[j]) {
			;[heap[i], heap[j]] = [heap[j], heap[i]]

			// i 更新为被交换的孩子结点的索引
			i = j
			// j 更新为孩子结点的左孩子的索引
			j = j * 2 + 1
		} else {
			break
		}
	}
}

// 向堆中添加元素
function upHeap(low, heigh, heap) {
	let i = heigh
	let j = Math.floor((i - 1) / 2) // 当前节点的父节点

	while (i >= low) {
		if (heap[j] < heap[i]) {
			;[heap[i], heap[j]] = [heap[j], heap[i]]

			i = j
			j = Math.floor((i - 1) / 2)
		} else {
			break
		}
	}
}
